package main

import (
	"fmt"
)

//维护一个正序数组,二分查找插入：364ms 19%，23.1MB 8%
type MedianFinder struct {
	slice []int
	len   int
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
	return MedianFinder{
		slice: []int{},
		len:   0,
	}
}

func (m *MedianFinder) AddNum(num int) {
	if m.len == 0 || num >= m.slice[m.len-1] {
		m.slice = append(m.slice, num)
		m.len++
		return
	}
	if num <= m.slice[0] {
		m.slice = append([]int{num}, m.slice...)
		m.len++
		return
	}

	l, r := 0, m.len-1
	M := (l + r) / 2
	for l < r && num != m.slice[M] {
		if num > m.slice[M] {
			l = M + 1
		} else if num < m.slice[M] {
			r = M - 1
		}
		M = (l + r) / 2
	}
	if num < m.slice[M] {
		m.slice = append(m.slice[:M], append([]int{num}, m.slice[M:]...)...)
	} else {
		m.slice = append(m.slice[:M+1], append([]int{num}, m.slice[M+1:]...)...)
	}
	m.len++
}

func (m *MedianFinder) FindMedian() float64 {
	if m.len == 0 {
		return 0
	}
	Median := m.len / 2
	if m.len%2 == 1 {
		return float64(m.slice[Median])
	} else {
		return (float64(m.slice[Median]) + float64(m.slice[Median-1])) / 2
	}
}

func main() {
	Median := Constructor()
	fmt.Println(Median.FindMedian())
	Median.AddNum(45)
	Median.AddNum(1)
	Median.AddNum(2)
	fmt.Println(Median.FindMedian())
}
